1. Field
The present disclosure relates to network route lookup. More specifically, the present disclosure relates to a method and system for efficiently representing and accessing sparsely distributed network address prefixes.
2. Related Art
The relentless growth of the Internet has brought with it an insatiable demand for bandwidth. As a result, equipment vendors race to build larger, faster, and more versatile routers to move traffic, especially in the core networks. However, such a router is typically coupled to a large number of other routers through a plurality of network interfaces and can forward traffic to a large number of sub-networks. Consequently, the router needs to maintain forwarding information, such as network address prefixes, for all sub-networks and interfaces in a database, known as a Forwarding Information Base (FIB).
Upon receiving a packet, the router performs a network address lookup. The lookup process finds the longest match between the destination address of the packet and a network address prefix and determines the corresponding outgoing interface. Hence, storing and accessing such information efficiently and intelligently can improve the lookup process, and thereby one of the most challenging problems in today's networking paradigm.
Trie lookup is one of the most popular network address lookup techniques used in a router. A trie is a tree data structure, wherein the position of a node in the tree represents a corresponding key. Particularly for representing network address prefixes in an FIB, a node in a trie represents a longest prefix match up to the position of the node. The lookup technique using a trie can be further improved with a multi-bit trie that examines multiple bits from a network address for a lookup. Such a multi-bit trie-based lookup works particularly well for densly populated tries. However, with the increasing popularity of Virtual Private Network (VPN) and Internet Protocol (IP) version 6 (IPv6), prefixes in an FIB have become sparsely populated. Consequently, the traditional multi-bit trie-based lookup techniques have become ill-equipped to efficiently store and access these sparsely populated tries.